﻿#light

module PDA

open System
open System.Collections.Generic

///hack to use some ordinal type for state right now. I'll figure out a better implementation later
type State = 
    | q0 = 0
    | q1 = 1
    | q2 = 2
    | q3 = 3
    
//our types that we'll need. Defined for ease of member data access. Tuples may be used in the future at some point
type Config = { state:State; input:list<char>; stack:list<char>; }
type Move = { state:State; stack:list<char>; }
type Moves = list<Move>

//testing with tuple definitions to get rid of some verbosity
type Config' = State * list<char> * list<char>
type Move' = State * list<char>
type Moves' = list<Move'>

///think of this as Min([], list - 1)
let combSub s = 
    match s with
    | h :: t -> t
    | [] -> []

let head s =
    match s with
    | h :: t -> [h]
    | [] -> []
    
///helper function
let normalizeConfig (cfg:Config) = 
    {state=cfg.state; input=head cfg.input; stack= head cfg.stack;}

///this should lazily generate our sequence of new configurations.
let getConfigs (cfg :Config, moves :Moves, lambdas :Moves) :seq<Config> =
    seq { for move in moves do
            yield {state=move.state; input=combSub cfg.input; stack=move.stack @ combSub cfg.stack;}
          for move in lambdas do
            yield {state=move.state; input=cfg.input; stack=move.stack @ combSub cfg.stack;}
        }

let isEmpty cfg =
    match cfg.input with
    | [] -> printfn "accepted"
            true
    | _ ->  printfn "crash"
            false
    
///the actual powerhouse
let rec runArg (accept:State, getMoves, cfg:Config, acc) : bool = 
    seq {0..acc} |> Seq.iter(fun(n) -> printf "\t")
    printfn "|- (%O, %A, %A)" cfg.state cfg.input cfg.stack
    match cfg.state with
    | _ when accept = cfg.state -> isEmpty cfg
    | _ ->  
            let moves, lambdas = getMoves cfg
            match (moves, lambdas) with
            | ([], []) ->   printfn "crash"
                            false
            | _ ->  getConfigs(cfg, moves, lambdas)
                    |> Seq.exists(fun(c :Config) -> runArg(accept, getMoves, c, acc+1))
                                     

let rec buildDict(rules, dict) = 
    match rules with
    | h :: t -> let cfg, moves:Config * Moves = h
                dict.[cfg] <- moves
                buildDict(t, dict)
    | [] -> dict
    

let createDict rules =
    buildDict(rules, new Dictionary<Config, Moves>())
    
///this will be our main function
let parseString (state, rules, cfg) = 
    match rules with
    | [] -> printfn "Please pass in rules"
            false
    | _ ->  let rulesdict = createDict rules
    
            let getLambdas (c :Config) =
                match c.input with
                | h :: t -> normalizeConfig {state=c.state; input=[]; stack=c.stack} |> rulesdict.TryGetValue
                | [] ->     false, []
                
            let getMoves c =
                let nc = normalizeConfig c
                let ok, moves = rulesdict.TryGetValue nc
                let ok2, lambdas = getLambdas nc                
                if ok && ok2 then 
                    moves, lambdas
                else if ok then 
                    moves, []
                else if ok2 then 
                    [], lambdas
                else [], []
            runArg(state, getMoves, cfg, 0)

          
    